<html>

<head>
<title>Round Trip</title>
</head>

<body>
<center>
<h1>CEOI 2001 Day 1 Problem 3</h1>
<h1>Round Trip</h1>
</center>

    <p ALIGN="JUSTIFY">Your team decided to take a round trip
    in the host country after the competition. You want to travel to a
    destination city and return to the starting city. The only requirement your
    team specified is that the forward route to the destination city and the
    return route back to the starting city must contain the least possible
    number of common roads. (A route can not contain any road twice or more
    times.)</p>
    <p ALIGN="JUSTIFY">You are to write a program that
    computes two routes between the starting city and the destination city so
    that the number of common roads in the two routes is as small as possible.</p>
    <h2>Input</h2>
    <p ALIGN="JUSTIFY">The first line of the file trip.in
    contains two integers, <i>S</i> and <i>D</i> (<i>S</i>  &lt;&gt; <i>D</i>), the
    labels of the starting and the destination cities, respectively. The second
    line contains two integers, <i>N</i> and <i>M</i>, where <i>N</i> (3&lt;= <i>N&lt;=
    </i>1000) is the number of the cities and <i>M</i> (2&lt;= M &lt;=
    100000) is the number of the roads between the cities. The cities are
    labeled from 1 to <i>N. </i>Each of the next <i>M</i> lines in the file
    contains two integers, <i>P</i> and <i>Q</i> (1&lt;= <i>P</i>, <i>Q</i>
    &lt;= <i>N</i>, <i>P</i> &lt;&gt; <i>Q</i>), meaning that there is a two-way
    road between city <i>P</i> and city <i>Q</i>. There is at most one road
    between any two cities.</p>
    <h2>Output</h2>
    <p ALIGN="JUSTIFY">The first line of the file trip.out
    must contain one integer, the least possible number of common roads of the
    forward and the return routes. The second line should contain a forward
    route as a sequence of city labels, including the starting and ending city.
    The third line should contain a return route as a sequence of city labels
    (again including the starting and ending cities). If there are more possible
    pairs of routes with the same least number of common roads then your program
    may output any one of them. If there is no route from the starting city to
    the destination city then the first and only line must contain -1.</p>
    <h2>Example</h2>
    <table BORDER="1" CELLSPACING="1" CELLPADDING="1" WIDTH="378">
      <tr>
        <td WIDTH="50%" VALIGN="TOP">trip.in</td>
        <td WIDTH="50%" VALIGN="TOP">trip.out</td>
      </tr>
      <tr>
        <td WIDTH="50%" VALIGN="TOP">
          1 6<br>
          7 8<br>
          2 1<br>
          1 3<br>
          2 3<br>
          4 2<br>
          4 5<br>
          5 6<br>
          7 5<br>
          6 7</td>
        <td WIDTH="50%" VALIGN="TOP">
          2<br>
          1 3 2 4 5 7 6<br>
          6 5 4 2 1</td>
      </tr>
    </table>
    <h2>Grading</h2>
    <p ALIGN="JUSTIFY">If the first line of the output file
    contains the correct answer then you obtain 2 points. If the first line
    contains a correct solution and the second and third lines contain correct
    routes then you obtain 3 additional points.</p>
    </td>
  </tr>
</table>
</div>
</body>

</html>
